#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e5 + 5;
const ll INF = 1e18;

int n, m;
int mnp[N], primes[N], tot;
void init(int n) {
  mnp[1] = 1;
  rep(i, 2, n) {
    if (!mnp[i]) mnp[i] = i, primes[++tot] = i;
    rep(j, 1, tot) {
      ll k = 1ll * primes[j] * i;
      if (k > n) break;
      mnp[k] = primes[j];
      if (i % primes[j] == 0) break;
    }
  }
}
struct Seg {
  ll l, r;
  bool operator<(const Seg& o) const { return l < o.l; }
};
vector<Seg> a[N];
void solve() {
  cin >> n;
  int mx = 1;
  rep(i, 1, n) {
    int p, q;
    cin >> p >> q;
    a[p].push_back({1, q});
    mx = max(mx, p);
  }
  ll ans = 0;
  per(i, mx, 2) {
    if (a[i].empty()) continue;
    vector<pii> nxt;
    int x = i - 1;
    while (x != 1) {
      int p = mnp[x], k = 0;
      while (x % p == 0) x /= p, k++;
      nxt.push_back({p, k});
    }
    sort(a[i].begin(), a[i].end());
    Seg pre{-1, -2};
    for (Seg now : a[i]) {
      if (pre.r + 1 >= now.l)
        pre.r += now.r + 1 - now.l;
      else {
        // pass to nxt
        if (pre.r >= pre.l) {
          for (pii p : nxt) {
            a[p.first].push_back(
                {pre.l + 1, pre.l + (pre.r + 1 - pre.l) * p.second});
          }
        }
        pre = now;
      }
    }
    if (pre.r >= pre.l) {
      for (pii p : nxt) {
        a[p.first].push_back(
            {pre.l + 1, pre.l + (pre.r + 1 - pre.l) * p.second});
      }
    }
    ans = max(pre.r, ans);
    a[i].clear();
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init(1e5);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}